import collections


class Solution(object):
    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        k = len(strs)
        strs = [collections.Counter(s) for s in strs]
        strs = [(s['0'], s['1']) for s in strs]
        max_v = 0
        DP = [collections.defaultdict(int) for _ in range(k)]
        DP[0][(0, 0)] = 0

        def cmp(s):
            if s[0] <= m and s[1] <= n:
                return True
            else:
                return False

        if cmp(strs[0]):
            DP[0][strs[0]] = 1
            max_v = 1
        for i in range(1, k):
            for key in DP[i - 1]:
                DP[i][key] = max(DP[i - 1][key], DP[i][key])
                new_value = (key[0] + strs[i][0], key[1] + strs[i][1])
                if cmp(new_value):
                    DP[i][new_value] = max(DP[i][new_value], DP[i - 1][key] + 1)
                    max_v = max(max_v, DP[i][new_value])
        return max_v


data = Solution()
strs = ["10", "0001", "111001", "1", "0"]
m = 5
n = 3
print(data.findMaxForm(strs, m, n))
